/**
 * //给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可
 * //能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * // 输入: 12258
 * //输出: 5
 * //解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 0 <= num < 2³¹
 * //
 * //
 * // Related Topics 字符串 动态规划 👍 480 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID_Offer_46_BaShuZiFanYiChengZiFuChuanLcof {
    public static void main(String[] args) {
        Solution solution = new ID_Offer_46_BaShuZiFanYiChengZiFuChuanLcof().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int translateNum(int num) {

            if (num < 10) return 1;

            char[] arr = Integer.valueOf(num).toString().toCharArray();

            int n = arr.length;

            //dp[i] = dp[i-1] + dp[i-2]( 10 < i-2 < 26 )

            //推导最终状态，只需要保留 i-1 和 i-2即可
            int i2 = 1; //第0个数字只有1种翻译方式
            int i1 = 1; //第1个数字一开始只有一种翻译方式
            if (parseLastAbleToTrans(arr[1], arr[0])) { //如果 i2 + i1 能转译， 就多了一种
                i1++;
            }


            //从第2个字母开始推导
            for (int i = 2; i < n; i++) {
                int tmp = i1; //如果当前数字只当作单数翻译，那前面的翻译方式就有i1种。

                //判断是否能加上前面的值变为其他翻译
                char now = arr[i];
                char last = arr[i - 1];
                if (parseLastAbleToTrans(now, last)) {
                    tmp += i2;
                }

                i2 = i1;
                i1 = tmp;
            }

            return i1;


        }

        private boolean parseLastAbleToTrans(char now, char last) {
            StringBuilder sb = new StringBuilder();
            sb.append(last).append(now);
            int addLast = Integer.parseInt(sb.toString());
            if (9 < addLast && addLast < 26) {
                return true;
            }
            return false;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}